# -*- coding: utf-8 -*-            
# @Time : 2022/11/8 22:30
# @Author  : lining
# @FileName: single_stack.py
"""
单调栈
单调栈（monotone-stack）是指栈内元素（栈底到栈顶）都是（严格）单调递增或者单调递减的。
如果有新的元素入栈，栈调整过程中 会将所有破坏单调性的栈顶元素出栈，并且出栈的元素不会再次入栈 。由于每个元素只有一次入栈和出栈的操作，所以 单调栈的维护时间复杂度是O(n) 。

单调栈性质：
• 单调栈里的元素具有单调性。
递增（减）栈中可以找到元素左右两侧比自身小（大）的第一个元素。

题目
给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。

求在该柱状图中，能够勾勒出来的矩形的最大面积。
https://leetcode.cn/problems/largest-rectangle-in-histogram/
heights = [2,1,5,6,2,3]
解题思路：
（1）单调递增栈，确保所有数据出栈，在列表最后追加一个0，比所有数字都小的数，避免遍历完原列表还要手动出栈
（2）比当前高度大的数据要出栈，但是比当前高度小的还在栈顶，解决方法，把这些高度出栈，但是把宽度加到当前要入栈的这根柱子的宽度上
比如  1，2，3，4，1，最后一个1，2，3，4要出栈，先把2，3，4出栈，计算好面积，保存，把这三个的宽度3，加上原来的宽度1，变成一个高度为1，宽度为4的方块入栈
（3）当前高度大于前一个的高度，入栈。当前高度小于前一个高度，先出栈，直到栈顶高度小于当前高度，把当前高度入栈
"""
class Solution(object):
    def largestRectangleArea(self, heights):
        """
        :type heights: List[int]
        :rtype: int
        """
        # 先保存一下所有可能出现的面积
        area = []
        # 栈，保存单调栈,数据格式为[宽，高]，宽度默认为1
        stack = []
        # 放入一个最小的数，保证全部都能出栈
        heights.append(0)
        for i in heights:
            # 初始宽度
            width = 0
            # 当前高度比前一个高度矮，出栈，计算面积，一直到比前一个高度高
            while stack and i < stack[-1][1]:
                x = stack.pop()
                height = x[1]
                width = width + x[0]
                area.append(height*width)
            # 当前高度比前一个高度高，入栈
            stack.append([width+1, i])
        print(area)


heights = [2,1,5,6,2,3]
Solution().largestRectangleArea(heights)


